package com.lanren;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        System.out.println("插入排序");
        int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7, 4, 10};
        System.out.println("插入排序前：" + Arrays.toString(array));
        sort(array);
        System.out.println("插入排序后：" + Arrays.toString(array));

    }

    /**
     * 移位法
     */
    public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int length = a.length;//数组长度，将这个提取出来是为了提高速度。
        int num;//要插入的数
        for (int i = 1; i < length; i++) {//插入的次数
            num = a[i];//要插入的数
            int j = i - 1;//已经排序好的序列元素个数
            while (j >= 0 && a[j] > num) {//序列从后到前循环，将大于insertNum的数向后移动一格
                a[j + 1] = a[j];//元素移动一格
                j--;
            }
            a[j + 1] = num;//将需要插入的数放在要插入的位置。
        }
    }
}
